3736. Золотой песок

Во время ограбления магазина вор обнаружил n ящичков с золотым песком. Весь песок в ящичке под номером i имеет стоимость v_i и вес w_i. Чтобы унести награбленное, вор использует рюкзак. Требуется определить наибольшую суммарную стоимость песка, который может унести грабитель, если грузоподъёмность рюкзака ограничена величиной w.

Из ящичков можно пересыпать любое количество песка, тогда отношение стоимости отсыпанного песка к стоимости всего ящика будет равно отношению объёма отсыпанного песка к объёму всего ящика.

Вход. В первой строке записаны два целых числа n и w (1 ≤ n ≤ 1000, 1 ≤ w ≤ 10⁶). Далее следует n строк по два целых числа в каждой. В i-ой строке записана стоимость v_i и вес w_i песка в i-ом ящике. Все числа неотрицательные и не превосходят 10⁶.

Выход. Выведите искомую максимальную стоимость с точностью до 3 знаков после запятой.

Пример входа	Пример выхода
3 50 60 20 100 50 120 30	180.000

РЕШЕНИЕ

жадность - рюкзак

Анализ алгоритма

Стоимость единицы веса песка в i-ом ящике составляет v_i / w_i. Очевидно, что рюкзак следует грузить как можно более дорогим песком. Отсортируем ящики по невозрастанию стоимости единицы песка (по невозрастанию v_i / w_i). Для загрузки рюкзака воспользуемся жадным подходом.

Пример

Отсортируем ящики песка по невозрастанию отношения v_i / w_i.

Грабитель может унести с собой w = 50 песка. Он берет с собой:

· 30 единиц песка общей стоимостью 120;

· 20 единиц песка общей стоимостью 60;

Таким образом общая стоимость его прибыли составит 180.

Реализация алгоритма

Объявим класс Sand, который содержит цену песка price (за единицу) и вес имеющегося в наличии песка weight стоимости price.

class Sand

{

public:

double price;

int weight;

Sand(double price, int weight) : price(price), weight(weight) {}

};

Функция f является компаратором для сортировки песка. Песок сортируется по убыванию его стоимости.

int f(Sand a, Sand b)

{

return a.price > b.price;

}

Читаем входные данные. Заносим в массив v пары: стоимость единицы песка и вес песка в ящике.

scanf("%d %d", &n, &w);

for (i = 0; i < n; i++)

{

scanf("%d %d", &vi, &wi);

v.push_back(Sand(1.0 * vi / wi, wi));

}

Сортируем ящики по невозрастанию стоимости единицы песка.

sort(v.begin(), v.end(), f);

Грузим жадно рюкзак. Вес песка, который еще можно загрузить в рюкзак, равен w. Берем i-ый ящик. В рюкзак можно положить вес не более min(w, вес i-го ящика).

for (i = 0; i < v.size(); i++)

{

res += min(w, v[i].weight) * v[i].price;

w -= min(w, v[i].weight);

}

Выводим стоимость песка в рюкзаке.

printf("%.3lf\n", res);